package top.dprkshow.practice.quicksort;

import edu.princeton.cs.algs4.StdRandom;

/**
 * @author Kent HAN
 * @date 2021/9/3
 */
public class QuickSorter {
    public void sort(int[] arr) {
        StdRandom.shuffle(arr);
        sort(arr, 0, arr.length - 1);
    }

    private void sort(int[] arr, int low, int high) {
        if (low > high) {
            return;
        }
        int i = low, lt = low, gt = high;
        while (i <= gt) {
            if (arr[i] < arr[lt]) {
                swap(arr, i, lt++);
            } else if (arr[i] > arr[lt]) {
                swap(arr, i, gt--);
            } else {
                i++;
            }
        }
        sort(arr, low, lt - 1);
        sort(arr, gt + 1, high);
    }

    private void swap(int[] arr, int indexA, int indexB) {
        int tmp = arr[indexA];
        arr[indexA] = arr[indexB];
        arr[indexB] = tmp;
    }
}
